#define _CRT_SECURE_NO_WARNINGS
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N];
//int n;
//int main()
//{
//	cin >> n;
//	long long ret = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//	}
//	sort(a + 1, a + n + 1);
//	for (int i = 1; i <= n / 2; i++)
//	{
//		ret +=a[n + 1 - i]-a[i];
//	}
//	cout << ret << endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 2e5 + 10;
//int a[N];
//int n;
//int main()
//{
//	cin >> n;
//	int ret = -1e6,sum=0;
//	for (int i = 1; i <= n; i++)
//	{
//		int x; cin >> x;
//		sum += x;
//		ret = max(ret, sum);
//		if (sum < 0) sum = 0;
//	}
//	cout << ret << endl;
//	return 0;
//}
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 3e4 + 10;
//int w, n;
//int a[N];
//int main()
//{
//	cin >> w >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//	}
//	sort(a + 1, a + n + 1);
//	int l = 1, r = n,cnt=0;
//	while (l <= r)
//	{
//		if (a[l] + a[r] <= w) l++, r--;
//		else r--;
//		cnt++;
//	}
//	cout << cnt << endl;
//	return 0;
//}
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1e3 + 10;
//struct node
//{
//	int index;
//	int cnt;
//}r[N], c[N];
//int m, n, k, l, d;
//bool cmp1(node& x,node& y)
//{
//	return x.cnt > y.cnt;
//}
//bool cmp2(node& x, node& y)
//{
//	return x.index < y.index;
//}
//int main()
//{
//	cin >> m >> n >> k >> l >> d;
//	for (int i = 1; i <= m; i++) r[i].index = i;
//	for (int i = 1; i <= n; i++) c[i].index = i;
//	while (d--)
//	{
//		int x, y, p, q;
//		cin >> x >> y >> p >> q;
//		if (x == p)
//		{
//			int tmp = min(y, q);
//			c[tmp].cnt++;
//		}
//		else
//		{
//			int tmp = min(x, p);
//			r[tmp].cnt++;
//		}
//	}
//	sort(r + 1, r + m + 1,cmp1);
//	sort(c + 1, c + n + 1, cmp1);
//	sort(r + 1, r + k + 1, cmp2);
//	sort(c + 1, c + 1 + l,cmp2);
//	for (int i = 1; i <= k; i++) cout << r[i].index<<" ";
//	cout << endl;
//	for (int i = 1; i <= l; i++) cout << c[i].index<<" ";
//	cout << endl;
//	return 0;
//}
//#include<iostream>
//#include<algorithm>
//#include<cstring>
//using namespace std;
//const int N = 20;
//int a[N][N];
//int c[N]; 
//int n, m, k;
//int cal(int x)
//{
//	int cnt = 0;
//	while (x)
//	{
//		cnt++;
//		x = x & x - 1;
//	}
//	return cnt;
//}
//bool cmp(int x, int y)
//{
//	return x > y;
//}
//int main()
//{
//	cin >> n >> m >> k;
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < m; j++)
//		{
//			cin >> a[i][j];
//		}
//	}
//	int ret = 0;
//	for (int st = 0; st < (1 << n); st++)
//	{
//		int t = cal(st);
//		if (t > k) continue;
//		memset(c, 0, sizeof c);
//		int sum = 0;
//		for (int i = 0; i < n; i++)
//		{
//			for (int j = 0; j < m; j++)
//			{
//				if ((st >> i) & 1) sum += a[i][j];
//				else c[j] += a[i][j];
//			}
//		}
//		sort(c, c + m,cmp);
//		for (int i = 0; i < min(m,k-t); i++) sum += c[i];
//		ret = max(ret, sum);
//	}
//	cout << ret << endl;
//	return 0;
//}
//#include<iostream>
//#include<algorithm>.
//using namespace std;
//const int N = 25;
//string s[N];
//int n;
//bool cmp(string& x, string& y)
//{
//	return x + y > y + x;
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> s[i];
//	}
//	sort(s + 1, s + n + 1, cmp);
//	for (int i = 1; i <= n; i++) cout << s[i];
//	return 0;
//}
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1e5 + 10;
//int n;
//struct node
//{
//	int d;
//	int t;
//}a[N];
//bool cmp(node& x, node& y)
//{
//	return x.t * y.d < x.d * y.t;
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i].t>>a[i].d;
//	sort(a + 1, a + 1 + n, cmp);
//	long long ret = 0;
//	int t = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		ret += a[i].d * t;
//		t += 2 * a[i].t;
//	}
//	cout << ret << endl;
//	return 0;
//}
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 5e4 + 10;
//struct node
//{
//	int w;
//	int s;
//}a[N];
//int n,sum;
//bool cmp(node& x, node& y)
//{
//	return max(-y.s,y.w-x.s) >max(-x.s,x.w-y.s);
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i].w >> a[i].s,sum+=a[i].w;
//	sort(a + 1, a + 1 + n, cmp);
//	int ret =-1e9-10,w=0;
//	for (int i = 1; i <= n; i++)
//	{
//		ret = max(ret, w - a[i].s);
//		w += a[i].w;
//	}
//	cout << ret << endl;
//	return 0;
//}